package leetcode

import (
	"gitee.com/ombak/leetcode/pkg/list"
)

// recursively reverse linked list.
func reverseRecursively(a, b *list.ListNode) *list.ListNode {
	if a == b || a.Next == b {
		return a
	}
	last := reverseIteratively(a.Next, b)
	a.Next.Next = a
	a.Next = b
	return last
}

// iteratively reverse linked list
func reverseIteratively(a, b *list.ListNode) *list.ListNode {
	cur := a
	var pre *list.ListNode
	pre = nil
	for cur != b {
		nx := cur.Next
		cur.Next = pre
		pre = cur
		cur = nx
	}
	return pre
}

// https://leetcode.com/problems/reverse-nodes-in-k-group/
func reverseKGroup(head *list.ListNode, k int) *list.ListNode {
	if head == nil {
		return head
	}
	// reverse element from a to b: [a, b), does not include b
	a, b := head, head
	for i := 0; i < k; i++ {
		// left-out nodes, in the end, should remain as it is
		if b == nil {
			return head
		}
		b = b.Next
	}
	r := reverseRecursively(a, b)
	// sub linked list recursively
	a.Next = reverseKGroup(b, k)
	return r
}
